package string.滑动窗口;

import java.util.ArrayList;
import java.util.List;

/**
 * @Author kaho
 * @create 2020/11/30
 */
public class _438_找到字符串中所有字母异位词 {

    /**
     *给定一个字符串 s 和一个非空字符串 p，找到 s 中所有是 p 的字母异位词的子串，返回这些子串的起始索引。
     *
     * 字符串只包含小写英文字母，并且字符串 s 和 p 的长度都不超过 20100。
     *
     * 来源：力扣（LeetCode）
     * 链接：https://leetcode-cn.com/problems/find-all-anagrams-in-a-string
     * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
     * @param s
     * @param p
     * @return
     */
    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> r = new ArrayList<>();

        if (p.length()>s.length()) {
            return r;
        }

        int[] c1 = new int[26];
        int[] c2 = new int[26];

        for (int i = 0; i < p.length(); i++) {
            c1[s.charAt(i)-'a']++;
            c2[p.charAt(i)-'a']++;
        }

        for (int i = p.length(); i < s.length(); i++) {
            if (isEquals(c1,c2)){
                r.add(i-p.length());
            }
            c1[s.charAt(i-p.length())-'a']--;
            c1[s.charAt(i)-'a']++;
        }
        if (isEquals(c1,c2)){
            r.add(s.length()-p.length());
        }
        return r;

    }

    private boolean isEquals(int[] c1, int[] c2) {
        for (int i = 0; i < 26; i++) {
            if (c1[i]!=c2[i]) {
                return false;
            }

        }
        return true;
    }
}
